package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 这个和 102 一样啊
 * @author qidi
 * @date 2022-01-06 11:30:20
 */
class Q0107_BinaryTreeLevelOrderTraversalIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) return result;

            Deque<TreeNode> q = new ArrayDeque<>();
            Deque<TreeNode> next = new ArrayDeque<>();
            q.add(root);
            List<Integer> inner = new ArrayList<>();

            while (!q.isEmpty()) {
                TreeNode node = q.pop();
                inner.add(node.val);
                if (node.left != null) next.add(node.left);
                if (node.right != null) next.add(node.right);

                if (q.isEmpty()) {
                    result.add(0, new ArrayList<>(inner));
                    inner.clear();
                    q.addAll(next);
                    next.clear();
                }
            }

            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0107_BinaryTreeLevelOrderTraversalIi().new Solution();
    }
}